maxint=999999
pp=[
    [0,10,maxint,30,100],
    [10,maxint,50,maxint,maxint],
    [maxint,50,maxint,20,10],
    [30,maxint,20,maxint,60],
    [100,maxint,10,60,maxint],
    ]
pp=[
    [0,6,3,maxint,maxint,maxint],
    [6,0,2,5,maxint,maxint],
    [3,2,0,3,4,maxint],
    [maxint,5,3,0,2,3],
    [maxint,maxint,4,2,0,5],
    [maxint,maxint,maxint,3,5,0],
    ]
def calculate_path():
    s={0:0}
    u={1:1,2:2,3:3,4:4,5:5}
    i=0
    add_pos=[i]
    dist=pp[i]
    prev=i
    while True:
        minpos=maxint
        minp=maxint
        print i,':'
        for m in u.values():
            for n in s.values():
                if (dist[n]+pp[n][m])<dist[m]:
                    dist[m]=dist[n]+pp[n][m]
                #print dist
        for m in u.values():
            if dist[m]<minp:
                minpos=m
                minp=dist[m]
        print minpos,minp

        s[minpos]=minpos
        u.pop(minpos)
        add_pos.insert(0,minpos)
        print dist
        prev=i
        i=minpos

        print s.values(),u.values()
        if not u:
            break
    print add_pos
    print dist

#print pp

calculate_path()



'''
add_pos=[]
    i=0
    dist=pp[i]
    prev=i
    while True:
        minpos=maxint
        minp=maxint
        print i,':'
        for m in range(len(pp[i])):
            print m,prev,dist[i]+pp[i][m],minp
            if (dist[i]+pp[i][m])<minp and m!=prev:
                minpos=m
                minp=dist[i]+pp[i][m]
            if (dist[i]+pp[i][m])<dist[m]:
                dist[m]=dist[i]+pp[i][m]
        print minpos,minp
        #if (dist[i]+minp)<dist[minpos]:
            #dist[minpos]=dist[i]+minp
            #print minpos,minp,dist[minpos]
        print dist
        add_pos.insert(0,i)
        prev=i
        i=minpos
        
        if len(add_pos)>=5:
            break
    print add_pos
    print dist
'''





